package 回溯;

import java.util.*;

public class LeetCode90_子集 {
    public Set<Deque<Integer>> set = new HashSet<>();
    public List<List<Integer>> subset(int[] nums) {
        // 这个是可以看作是树的深度，走到最底层才输出
        int len = nums.length;

        List<List<Integer>> res = new ArrayList<>();
        if(len == 0) {
            return res;
        }
        // 路径变量
        Deque<Integer> path = new ArrayDeque<>();
        dfs(nums, len, 0, path,res);
        return res;
    }

    private void dfs(int[] nums, int len, int index, Deque<Integer> path, List<List<Integer>> res) {
        if(index == len) {
            set.add(path);
            if(!set.contains(path)) {
                res.add(new ArrayList<Integer>(path));
            }
            return;
        }
        // 不选择这个元素，直接进入下一层，
        dfs(nums, len, index + 1, path, res);
        path.addLast(nums[index]); // 考虑这个元素，加入它
        // 选择这个元素，进入下一层
        dfs(nums, len, index + 1, path, res);
        path.removeLast();
    }
}
